package hot100;

public class Solution309 {

    public int maxProfit(int[] prices) {
        // 分别对应dp[i-1][0]、dp[i-1][1]、dp[i-1][2]
        int last0 = -prices[0];
        int last1 = 0;
        int last2 = 0;
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            int current0 = Math.max(last0, last2 - prices[i]);
            int current1 = last0 + prices[i];
            int current2 = Math.max(last1, last2);
            maxProfit = Math.max(Math.max(current0, current1), current2);
            last0 = current0;
            last1 = current1;
            last2 = current2;
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        Solution309 solution309 = new Solution309();
        System.out.println(solution309.maxProfit(new int[]{1, 2, 3, 0, 2}));
    }
}
